#pragma once
#include "structures.h"

const size_t symbolcnt = 0x100;

std::string banner() {
	printf(
		"+----------------------------------------+\n"
		"| Arithmetic Encode And Decode Procedure |\n"
		"+----------------------------------------+\n"
	);
	std::string fname;
	std::cout << "Please enter the filename to encode and decode: \n";
	std::getline(std::cin, fname);
	return fname;
}

void collect_frequency(Freqperchar* freq, Freqperchar** freqp, char* filecontent, size_t filelength)
{
	size_t i;
	/* Initialize the frequency array (in frequency order)
	 and the corresponding pointer array (in alphabetical order) */
	for (i = 0; i < symbolcnt; i++) {
		freq[i].c = (unsigned char)i;
		freq[i].cnt = 0;
		freq[i].p = 0.0;
		freq[i].P = 0.0;
		freqp[i] = &freq[i];
	}
	/* loop the array to collect occurance counts */
	for (i = 0; i < filelength; i++)
		freq[(unsigned char)filecontent[i]].cnt++;
	/* sort the frequency array from large to small, not necessary */
	qsort(freq, symbolcnt, sizeof(Freqperchar), sortbycnt);
	qsort(freqp, symbolcnt, sizeof(Freqperchar*), sortbyc);
}

/* print the progress bar |=======>| */
void progress_bar(double progress, const char* phase)
{
	const size_t barlength = 50;
	size_t pg = (size_t)(progress * barlength), j = 0;
	printf("%s Progress |", phase);
	for (; j < pg; j++) putchar('=');
	putchar('>');
	for (; j < barlength; j++) putchar(' ');
	printf("| %.2lf%%\r", progress * 100);
	fflush(stdout);
}


/* This function is the critical part of the whole Arithmetic Algorithm 
 * Since the double of c++ has limited precision, the probability of 
 * each p should have the form of 2^{-K}, which will not lose precision
 * during divide.
 * Huffman tree is used to achieve this goal, ie, reassign the p of each
 * symbol
 */
void p_unify(Freqperchar* freq, const Freqperchar* eptr)
{
	Freqperchar* fptr = nullptr;
	/* make the head node of the entire list */
	ListNode* listhead = (ListNode*)malloc(sizeof(ListNode));
	listhead->cnt = 0;
	listhead->tree = NULL;
	listhead->next = NULL;
	/* insert linked node in the reverse order */
	for (fptr = freq; fptr < eptr; fptr++) {
		ListNode* newlistnode = (ListNode*)malloc(sizeof(ListNode));
		newlistnode->next = listhead->next;
		newlistnode->cnt = fptr->cnt;
		TreeNode* newtreenode = (TreeNode*)malloc(sizeof(TreeNode));
		newtreenode->cnt = fptr->cnt;
		newtreenode->leaf = fptr;
		newtreenode->left = NULL;
		newtreenode->right = NULL;
		newlistnode->tree = newtreenode;
		listhead->next = newlistnode;
	}
	// Implement Huffman Algorithm
	while (listhead->next && listhead->next->next) {
		ListNode* first = listhead->next;
		ListNode* second = first->next;
		// printf("find first->c %02x and second->c %02x")
		size_t cnt = first->cnt + second->cnt;
		ListNode* insert = second;
		while (insert->next && insert->next->cnt <= cnt) /* points to the node before insertion */
			insert = insert->next;
		/* create a new listnode and delete the original two */
		ListNode* newlistnode = (ListNode*)malloc(sizeof(ListNode));
		newlistnode->next = insert->next;
		newlistnode->cnt = cnt;
		TreeNode* newtreenode = (TreeNode*)malloc(sizeof(TreeNode));
		newtreenode->cnt = cnt;
		newtreenode->leaf = NULL;
		newtreenode->left = first->tree;
		newtreenode->right = second->tree;
		newlistnode->tree = newtreenode;
		insert->next = newlistnode;
		listhead->next = second->next;
		free(first);
		free(second);
	}
	/* once finished, there will be only one node in the list, with the pointer to the tree */
	const TreeNode* tree = listhead->next->tree;
	assigncode(tree, 0);

	free(listhead);
}


void checkencoding(Freqperchar** freqp)
{
	size_t i;
	for (i = 0; i < symbolcnt; i++) {
		printf("char at %02lx and p = %.20lf\n",
			i, freqp[i]->p);
	}
}

void printsymtab(Freqperchar* freq)
{
	printf("\n==========Symbol List============\n");
	size_t i;
	for (i = 0; i < symbolcnt; i++) {
		if (freq[i].cnt == 0) break;
		printf("Symbol 0x%02x, P = %.18lf, p = %.18lf, zone [%.12lf, %.12lf)\n",
			freq[i].c, freq[i].P, freq[i].p, freq[i].P, freq[i].P + freq[i].p);
	}
	printf("==========Symbol List End============\n\n");
}
